#include<bits/stdc++.h>
using namespace std;

bool RED = true;
bool BLACK = false;

struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* p = nullptr;
    bool color;
    Node(int k):key(k){};
};

Node* nil = nullptr;

struct Tree {
    Node* root = nil;
};

bool color(Node* node) {
    return nil == node ? BLACK : node->color;
}

void dyeBlack(Node* node) {
    if (nil != node) {
        node->color = BLACK;
    }
}

void dyeRed(Node* node) {
    if (nil != node) {
        node->color = RED;
    }
}

void LL(Tree* T, Node* node) {
    if (node != T->root) {
        if (node == node->p->left) {
            node->p->left = node->left;
        }
        if (node == node->p->right) {
            node->p->right = node->left;
        }
        node->left->p = node->p;
    } else {
        T->root = node->left;
    }
    Node* child = node->left->right;
    node->left->right = node;
    node->p = node->left;
    node->left = child;
}

void RR(Tree* T, Node* node) {
    if (node != T->root) {
        if (node == node->p->left) {
            node->p->left = node->right;
        }
        if (node == node->p->right) {
            node->p->right = node->right;
        }
        node->right->p = node->p;
    } else {
        T->root = node->right;
    }
    Node* child = node->right->left;
    node->right->left = node;
    node->p = node->right;
    node->right = child;
}

void LR(Tree* T, Node* node) {
    RR(T, node->left);
    LL(T, node);
}

void RL(Tree* T, Node* node) {
    LL(T, node->right);
    RR(T, node);
}

void insertFixUp(Tree* T, Node* z) {
    while (z != T->root && z->p->color == RED) {
        Node* p = z->p;
        Node* f = p->p;
        if (p == f->left) {
            Node* y = f->right;
            if (color(y) == RED) {
                dyeBlack(y);
                dyeBlack(p);
                dyeRed(f);
                z = f;
            } else {
                if (z == p->right) {
                    RR(T, p);
                    z = p;
                    p = z->p;
                }
                dyeBlack(p);
                dyeRed(f);
                LL(T, f);
                z = T->root;
            }
        } else {
            Node* y = f->left;
            if (color(y) == RED) {
                dyeBlack(y);
                dyeBlack(p);
                dyeRed(f);
                z = f;
            } else {
                if (z == p->left) {
                    LL(T, p);
                    z = p;
                    p = z->p;
                }
                dyeBlack(p);
                dyeRed(f);
                RR(T, f);
                z = T->root;
            }
        }
    }
    dyeBlack(T->root);
}

void rb_insert(Tree* T, Node* z) {
    Node* y = nil;
    Node* x = T->root;
    while (x != nil) {
        y = x;
        if (x->key > z->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    if (nil == y) {
        T->root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
    z->p = y;
    dyeRed(z);
    insertFixUp(T, z);
}

Node* findMin(Node* root) {
    Node* cur = root;
    while (nil != cur->left) {
        cur = cur->left;
    }
    return cur;
}

void transplant(Tree* T, Node* a, Node* b) {
    if (T->root == a) {
        if (nil != b) {
            b->p = nil;
        }
        T->root = b;
        return;
    }
    Node* p = a->p;
    if (a == p->left) {
        p->left = b;
    } else {
        p->right = b;
    }
    if (nil != b) {
        b->p = p;
    }

}

void deleteFixUp(Tree* T, Node* x, Node* p) {
    while (x != T->root && color(x) == BLACK) {
        if (nil != x) {
            p = x->p;
        }
        if (x == p->left) {
            Node* s = p->right;
            if (color(s) == RED) {
                dyeBlack(s);
                dyeRed(p);
                RR(T, p);
            }
            if (color(s) && color(s->left) && color(s->right) == BLACK) {
                dyeRed(s);
                x = p;
            } else {
                if (color(s->right) == BLACK) {
                    LL(T, s);
                    s = p->right;
                }
                s->color = p->color;
                dyeBlack(p);
                RR(T, p);
                dyeBlack(s->right);
                x = T->root;
            }
        } else {
            Node* s = p->left;
            if (color(s) == RED) {
                dyeBlack(s);
                dyeRed(p);
                LL(T, p);
            }
            if (color(s) && color(s->left) && color(s->right)) {
                dyeRed(s);
                x = p;
            } else {
                if (color(s->left) == BLACK) {
                    RR(T, s);
                    s = p->left;
                }
                s->color = p->color;
                dyeBlack(p);
                LL(T, p);
                dyeBlack(s->left);
                x = T->root;
            }
        }
    }
    dyeBlack(x);
}

void rb_delete(Tree* T, Node* z) {
    bool originalColor = z->color;
    Node* x = nil;
    Node* y = z;
    Node* p;
    if (z == T->root) {
        p == nil;
    } else {
        p = z->p;
    }
    if (nil == y->left) {
        x = y->right;
        transplant(T, y, y->right);
    } else if (nil == y->right) {
        x = y->left;
        transplant(T, y, y->left);
    } else {
        y = findMin(z->right);
        x = y->right;
        originalColor = y->color;
        y->color = z->color;
        if (y != z->right) {
            p = y->p;
            transplant(T, y, y->right);
            y->right = z->right;
            y->right->p = y;
        } else {
            if (y == y->p->left) {
                y->p->left = nil;
            } else {
                y->p->right = nil;
            }
        }
        transplant(T, z, y);
        y->left = z->left;
        y->left->p = y;
    }
    delete z;
    if (BLACK == originalColor) {
        deleteFixUp(T, x, p);
    }
}

void print(Tree* T) {
    queue<Node*> q;
    if (nil != T->root) {
        q.emplace(T->root);
    }
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node* node = q.front();
            q.pop();
            if (nil == node) {
                cout << "NIL ";
                continue;
            }
            q.emplace(node->left);
            q.emplace(node->right);
            if (node->color == RED) {
                cout << "";
            } else {
                cout << "";
            }
            cout << node->key << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    Tree* T = new Tree();
    Node* root = new Node(14);
    Node* n1 = new Node(13);
    Node* n2 = new Node(2);
    Node* n3 = new Node(5);
    Node* n4 = new Node(7);
    Node* n5 = new Node(9);
    Node* n6 = new Node(11);
    Node* n7 = new Node(20);
    rb_insert(T, root);
    rb_insert(T, n1);
    rb_insert(T, n2);
    rb_insert(T, n3);
    rb_insert(T, n4);
    rb_insert(T, n5);
    rb_insert(T, n6);
    rb_insert(T, n7);
    print(T);
    rb_delete(T, n1);
    print(T);

    delete n1;
    delete n2;
    delete n3;
    delete n4;
    delete n5;
    delete n6;
    delete n7;
    delete root;
}
